"""全排列算法"""


class Permutation(object):
    @staticmethod
    def recursion(collection, permuation=[], start=0):
        """递归版本的全排列算法
        :param collection: 源集合
        :param permuation: 结果集合
        :param start:  递归起始点, 默认0
        :return:
        """
        if start == len(collection) - 1:
            permuation.append(', '.join("{0:>5}".format(str(x)) for x in collection))
            return
        i = start
        while i < len(collection):
            if i == start or collection[i] != collection[start]:
                collection[start], collection[i] = collection[i], collection[start]
                Permutation.recursion(collection, permuation, start + 1)
                collection[start], collection[i] = collection[i], collection[start]
            i += 1

    @staticmethod
    def dictionary(collection=[], permuation=[]):
        """字典序全排列算法
        :param collection: 源集合
        :param permuation: 结果集合
        :return:
        """
        collection.sort()
        while True:
            permuation.append(', '.join("{0:>5}".format(str(x)) for x in collection))

            j = len(collection) - 2
            index = 0
            while j >= 0:
                if collection[j] < collection[j+1]:
                    index = j
                    break
                j -= 1

            if j < 0:
                return

            j = len(collection) - 1
            while j >= 0:
                if collection[j] > collection[index]:
                    break;
                j -= 1

            collection[index], collection[j] = collection[j], collection[index]

            tail = collection[index + 1:]
            tail.reverse()
            collection[index + 1:] = tail



if __name__ == '__main__':
    result = []
    Permutation.dictionary([1, 2, 3, 4], result)
    for item in result:
        print(item)
